4.8 Arithmetic in Prolog

But there still remains a question: equality or inequality of what? - Aristotle, Politics

One of the uglier parts of Prolog is the way that it has many different ways to write equality or inequality, with subtly different shades of meaning. Here are some of them:

Unification

The = operator in Prolog attempts to unify two terms, and fails if it cannot.

The \= operator succeeds when given two terms that cannot be unified, but fails if they could unify (though Prolog does not unify them in that case, since the failure forces backtracking).

X = a.

Succeeds and defines X to a.

[X,a] = [b,Y].

Succeeds and defines X to b and Y to a.

 X = [Y].

Succeeds and defines X to be the list [Y] but leaves Y undetermined).

X = [X].

Perhaps surprisingly, succeeds and defines X to be the list [X]

This is implemented by defining X to be a linked list of length 1 whose only data is a pointer to the list itself.

It’s rather questionable whether this should be allowed, but detecting such pathological cases - known as an occurs check because it checks for circular definitions where the variable we are defining occurs in the proposed definition - would be extra work every unification. Since unification is such a fundamental operation in Prolog and executes so frequently, it was decided that doing the occur check would make Prolog too slow.

X \= Y.

Fails, since we could have made both sides equal by defining X to be Y or vice-versa.

X = 3, Y = 2, X = Y.

Fails, since by the time we get to X = Y, we have already decided that X must be 3 and Y must be 2, and there’s no way to make 3 unify with 2.

X = 3, Y = 2, X \= Y.

Succeeds, since by the time we get to X \= Y, we have decided that X must be 3 and Y must be 2, and it is correct to say that 3 cannot be unified with 2. ## Structural Equality

The operator == succeeds if the two terms are already the same, and fails otherwise. Unlike the unification operator =, the == operator never sets any variables.

The operator \= succeeds if the two terms are not the same, and fails if they are already the same.

Assume each of the following is a separate query (so that all variables start out unset in each case, and each query is independent of the others): > > prolog > X == a. > > > Fails, since X starts out unset and so is not yet the same as a. > > prolog > [X,a] == [b,Y]. > > > Fails, since the list [X,a] (containing an unset variable X) is not the same as the list [b,Y] (containing an unset variable Y). > > prolog > X == [X]. > > > Fails, since the unset variable X is not already equal to a list. > > prolog > X = [X], X == [X]. > > > Succeeds, since by the time we check X == [X] we have already use definition to make [X] the definition of X. > > prolog > 1+2 == 1+2. > > > Succeeds, since both sides are the same term. > > prolog > 1+2 == 2+1. > > > Fails, since 1+2 is literally a different term than 2+1. (Prolog does not evaluate terms like 1+2 unless we use specific operators like is to force that to happen!) > > prolog > X = 3, Y = 3, X==Y. > > > Succeeds, since by the time we get to X==Y we have defined both X and Y to be 3.

Arithmetic

The most important operator for doing arithmetic in Prolog is the is operator; this unifies the left-hand term with the evaluated value of the right-hand term.

Comparisons like < and =< (Prolog’s way of saying less-than-or-equal-to) evaluate both sides, and then succeed or fail based on the result of the comparison.

:::

 >   X is 5+2.
 >   ```
>
 >   Succeeds, and sets `X = 7` .
>
>    ```prolog
 >   X is Y*7.
 >   ```
 >   
 >   Fails, since `Y` is undefined and so we cannot evaluate `Y*7` to a value.
>
  >  ```prolog
  >  Y = 6, X is Y*7.
  >  ```
>
 >   Succeeds, and sets `Y = 6, X = 42`. The difference from the previous example is that by the time we need to calculate `Y*7`, we have already defined `Y` to be 7.
>
>    ```prolog
 >   1+2 is 2+1.
 >   ```
>
 >   Fails, since `is` only evaluates the right-hand-side, and the term `1+2` does not unify (cannot be made identical) to the value `3`.
>
 > (The operator `=:=` evaluates both sides and checks for equality, but it's rarely needed.)
## Doing Calculations

Newcomers to Prolog may be tempted to write

```prolog
fac(0) :- 1.
fac(X) :- X * fac(X-1).

fac(0, 1).  % Input 0 is related to output 1
fac(N, X) :- Nminus1 is N-1,
                fac(Nminus1, Nminus1Factorial),
                X is N * Nminus1Factorial.